package jly521.lucene.queries;

/**
 * @author Jly
 * @date 2020/1/16  19:40
 */
public class LevenshteinTest {

    public static int levenshtein(String str1,String str2) {
        int n = str1.length();
        int m = str2.length();
        if ( n == 0)
            return m;
        if ( m == 0)
            return n;
        int[][] Arr = new int[m + 1][n + 1];
        int cost = 0;
        for(int i=0;i<=n;i++)
            Arr[0][i] = i;
        for(int j=0;j<=m;j++)
            Arr[j][0] = j;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                if (str1.charAt(i-1) == str2.charAt(j-1))
                    cost = 0;
                else
                    cost = 1;
                Arr[j][i] = Arr[j-1][i]+1<Arr[j][i-1]+1?Arr[j-1][i]+1:Arr[j][i-1] +1 ;
                Arr[j][i] = Arr[j][i]<Arr[j-1][i-1]+cost?Arr[j][i]:Arr[j-1][i-1]+cost;
            }
        int nEdit = Arr[m][n];
        return nEdit;
    }

    public static void main(String[] args) {
        System.out.println(levenshtein("acdf", "acf"));
        System.out.println(111);
    }
}
